Trong
toán học và
khoa học máy tính, một
thuật toán, còn gọi là
giải thuật, là một
tập hợp hữu hạn các hướng dẫn
được xác định rõ ràng, có thể thực hiện được bằng máy tính, thường để giải quyết một lớp vấn đề hoặc để thực hiện một phép tính.
[1][2] Các thuật toán luôn
rõ ràng và được sử dụng chỉ rõ việc thực hiện các
phép tính,
xử lý dữ liệu,
suy luận tự động và các tác vụ khác.Là một
phương pháp hiệu quả, một thuật toán có thể được biểu diễn trong một khoảng không gian và thời gian hữu hạn,
[3] và bằng một ngôn ngữ hình thức được xác định rõ ràng
[4] để tính toán một
hàm số.
[5] Bắt đầu từ trạng thái ban đầu và đầu vào ban đầu (có thể
trống),
[6] các hướng dẫn mô tả một
phép tính, khi được
thực thi, sẽ tiến hành qua một số
[7] hữu hạn các trạng thái kế tiếp được xác định rõ, cuối cùng tạo ra "đầu ra"
[8] và chấm dứt ở trạng thái kết thúc cuối cùng. Sự chuyển đổi từ trạng thái này sang trạng thái tiếp theo không nhất thiết phải mang tính
xác định; một số thuật toán, được gọi là
thuật toán ngẫu nhiên, kết hợp đầu vào ngẫu nhiên.
[9]Khái niệm thuật toán đã tồn tại từ thời cổ đại.
Các thuật toán
số học, chẳng hạn như
thuật toán chia, được sử dụng bởi các
nhà toán học Babylon cổ đại vào khoảng 2500 TCN và các
nhà toán học Ai Cập vào khoảng 1550 TCN.
[10] Các nhà toán học Hy Lạp sau đó đã sử dụng các thuật toán trong
sàng Eratosthenes để tìm số nguyên tố,
[11] và
thuật toán Euclide để tìm
ước chung lớn nhất của hai số.
[12] Các nhà toán học Ả Rập như
al-Kindi vào thế kỷ thứ 9 đã sử dụng
các thuật toán
mật mã để
phá mã, dựa trên
phân tích tần số.
[13]Bản thân từ thuật toán (algorithm) từ bắt nguồn từ nhà toán học thế kỷ thứ 9
Muḥammad ibn Mūsā al-Khwārizmī, tên ông được Latinh hóa thành Algoritmi.
[14] Việc chính thức hóa một phần những gì sẽ trở thành khái niệm thuật toán hiện đại bắt đầu với nỗ lực giải
Entscheidungsproblem (vấn đề quyết định) do
David Hilbert đặt ra vào năm 1928. Các công thức hóa sau này được đóng khung như những nỗ lực để xác định "
khả năng tính toán hiệu quả "
[15] hoặc "phương pháp hiệu quả".
[16] Những công thức hóa đó bao gồm các
hàm đệ quy Gödel -
Herbrand -
Kleene của các năm 1930, 1934 và 1935,
phép tính lambda của
Alonzo Church năm 1936,
Công thức 1 của
Emil Post năm 1936 và các
máy Turing của
Alan Turing năm 1936–37 và 1939.